package org.example.myleet.p1588;

public class Solution {
    public int sumOddLengthSubarrays(int[] arr) {
        int n = arr.length;
        int[] preSum = new int[n + 1];
        preSum[0] = 0;
        preSum[1] = arr[0];
        for (int i = 1; i < n; ++i) {
            preSum[i + 1] = preSum[i] + arr[i];
        }
        int result = 0;
        for (int len = 1; len <= n; len += 2) {
            int idx;
            for (int i = 0; i < n && (idx = i + len) <= n; ++i) {
                result += preSum[idx] - preSum[i];
            }
        }
        return result;
    }
}
